package tree;

import java.util.Stack;

/**
 * Created by IntelliJ IDEA.
 * User: vinod.gupta
 */
public class BTree {
    private BTree left;
    private BTree right;
    private int data;

    public BTree() {
    }

    public BTree(BTree left, BTree right, int data) {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    public BTree getLeft() {
        return left;
    }

    public void setLeft(BTree left) {
        this.left = left;
    }

    public BTree getRight() {
        return right;
    }

    public void setRight(BTree right) {
        this.right = right;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    // InOrder Recursive
    public void inOrderTraversal() {
        if (this != null) {
            if (left != null)
                left.inOrderTraversal();
            System.out.println(data);
            if (right != null)
                right.inOrderTraversal();
        }
    }

    // Inorder Iterative
    public void inOrderTraversalIterative() {
        Stack<BTree> stack = new Stack<BTree>();
        boolean completed = false;
        BTree currentTree = this;
        while (!completed) {
            if (currentTree != null) {
                stack.push(currentTree);
                currentTree = currentTree.left;
            } else {
                if (!stack.empty()) {
                    currentTree = stack.pop();
                    System.out.println(currentTree.data);
                    currentTree = currentTree.right;
                } else
                    completed = true;
            }
        }
    }

    public static void main(String[] args) {

        // Created a random Tree.
        BTree tree = new BTree(null, null, 10);
        tree.setLeft(new BTree(null, null, 20));
        tree.setRight(new BTree(null, null, 30));
        tree.getLeft().setRight(new BTree(null, null, 40));
        tree.getLeft().setLeft(new BTree(null, null, 50));
        tree.getRight().setRight(new BTree(new BTree(new BTree(null, new BTree(null, null, 100), 110), new BTree(null, new BTree(null, new BTree(null, null, 70), 140), 80), 90), null, 60));

        System.out.println("Recursive Solution:");
        tree.inOrderTraversal();

        System.out.println("Iterative Solution: ");
        tree.inOrderTraversalIterative();

    }
}
